A communication network includes a plurality of stations connected to a common medium for communication. To coordinate transmission over such common medium by the stations of the network, communications on the network follow a prescribed multiple access technique or protocol. Such protocols determine the sequence of actions to be performed by each station to avoid or reduce the impact of interference arising from transmission by other stations.
Conventional widely used local-area networks (LANs) and metropolitan-area networks (MANs) fall into two broad categories: networks with a bus topology and networks with a ring topology. Networks which rely on ring topology (e.g. Token-Ring, FDDI etc.) use token-ring multiple access. Networks which rely on bus topology usually use carrier sense multiple access with collision detection (CSMA/CD) or token-bus multiple access.
Token-access techniques require transmission of control information (tokens) from one network node to another. In the event that the token is distorted, a fairly complicated token recovery procedure has to be initiated, which is a major limitation of token access.
Although the token-access methods are collision-free, they are difficult to implement, and local-area networks which use token access require high investments.
An example of the CSMA/CD protocol is disclosed in U.S. Pat. No. 4,063,220 issued on Dec. 13, 1977 to Metcalfe et al. In accordance with the CSMA/CD protocol, whenever any network station has a packet for transmission, it senses the communication medium, and if the medium is quiescent, the packet is impressed on the network. If the medium is engaged, the station waits and transmits its packet when it detects that the medium is idle. In view of signal propagation delay in the medium, it is possible that two or more stations may start transmitting on the medium almost simultaneously. These transmissions become scrambled and a collision appears in the network. Any packets that have collided must be retransmitted.
To control the adverse effect of collisions each transmitting station seeks to detect such collisions, and once a collision has been detected, transmission is interrupted and delayed for a randomly selected time interval set by the collision recovery procedure.
While the CSMA/CD protocol does facilitate successful data transmission between network stations, a considerable amount of time and medium throughput is lost whenever a collision occurs. Collision probability increases with traffic load, transmission rate and network length, and a higher collision probability results in a longer packet transmission delay. The CSMA/CD protocol cannot be used in real-time fault-tolerant networks with mixed topology, which may include interconnected sections with bus and ring topology, that do not lose connectivity when some of the channels are ruptured. It cannot be utilized for multi-priority distribution of the medium capacity among the network stations.
To improve the efficiency of CSMA/CD U.S. Pat. No. 4,598,285 issued Jul. 1, 1986 to Hoshen discloses a formula to improve average delay time after a collision in a communication network with the CSMA/CD protocol. However, while this method can decrease collision resolution time, it does not prevent the negative effect of collisions and it cannot be used in real-time networks with a fault-tolerant, mixed topology or for multi-priority capacity distribution.
Another modification of CSMA/CD (U.S. Pat. No. 4,628,311 issued Dec. 12, 1986 to Milling) assigns to each station an access window within a predetermined response period after the medium becomes idle. To distribute transmission capacity among the stations, the access windows available to all stations are assigned among them in rotation, providing all stations essentially equal access to the medium. If the medium has long been idle and the network nodes have no packets for transmission, and if the time assigned to the response has expired, any station which has a packet for transmission sends a special sync bit pattern to clock the network prior to transmitting its packet. Once the sync bit pattern has been transmitted each station again receives its access window and can transmit frames, if the medium is not seized first by another station with an earlier window. Although this patent is entitled "Carrier-Sense Multiple-Access with Collision Avoidance" (CSMA/CA), the inventor admits that his protocol, although reducing collision probability as it does, is unable to eliminate collisions altogether. Besides, the CSMA/CA protocol requires transmission of access control information to rotate the assignment of access windows. To achieve that, each frame has to contain, in its header, a window rotation control field. When a frame is distorted by unavoidable transmission errors, the network stations lose window rotation control information, which may lead to collisions. As the frame header has to be modified, a CSMA/CA network cannot use standard frame formats such as the Ethernet format. The protocol cannot be used in real-time networks with a fault-tolerant mixed topology or in networks with multi-priority distribution of the medium capacity.
Another collision avoidance scheme exists which assigns to each station an access window for determining the beginning of transmission after the medium becomes idle (U.S. Pat. No. 4,799,052 issued Jan. 17, 1989 to Near et al.). According to this patent, the time period between the instant the medium is released and the access window of a given station depends on the station's unique medium address number and also on the medium address number of the station which was the last to transmit before the medium became idle. However, this method also requires access control information to be passed through the network to determine whether or not a given station may send its packet. This information defines the medium address number of the station which is transmitting a frame. All frame headers must therefore include a special control field for the medium address number of the transmitting station. Similar to the previous scenario, no standard frames such as the Ethernet frame can be used with this protocol. Moreover, as in the previous scenario, the receiving station loses access control information if the frame is distorted in transmission, and recovery requires a special procedure. This protocol cannot be used in real-time networks with a fault-tolerant mixed topology or in networks with multi-priority medium capacity distribution.
The discussion above reveals that not one of the known protocols can be used for constructing multi-channel, real-time, fault-tolerant networks with a mixed topology and multi-priority distribution of the network medium capacity.
It would therefore be desirable to develop a collision-free protocol that does not require transmission of access control information within standard data frames; can be implemented without any changes in data frame formats; makes possible real-time networks with a mixed, fault-tolerant topology, which may include bus, star and ring sections; and which provides multi-priority distribution of the network medium capacity among the network stations.
It is therefore the main object of the invention to provide a transmission method and apparatus for stations with a common multi-channel communication medium which could be used to construct fault-tolerant networks, operational when one or more channels of the medium are broken.
It is another object of the present invention to provide a method and apparatus for multi-priority distribution of the network medium capacity between the network stations.
It is still another object of the present invention to provide a method and apparatus to accomplish collision-free, real-time packet transmission without transmission within data frames of any specific access control information, which makes it possible to use any frame formats, including standard ones.
In accordance with the present invention a method and apparatus are provided for data transmission on a multi-channel communication network, having a communication medium and a plurality of stations. The medium may comprise one or more communication channels with the same or different topology: bus, star, ring or mixed, including fault-tolerant topology. Each station may be connected to one or more communication channels for transmitting and receiving data, comprising data frames for information transmission and sync-signals for network synchronization. The channels may be point-to-point unidirectional or bidirectional ones for connecting two stations, one of which transmits data to the channel and the other receives the transmitted data from the channel. Alternately, the channels may be multipoint bidirectional, connecting more than two stations, each of which can transmit and receive data to/from the channel.
When a station has access to the medium it transmits its data to all output channels to which this station is connected. A station receives data from a single channel which has first become busy after an idle period, during which there was no data on any input channels connected to the station. The data received by a station from a selected input channel is retransmitted to all output channels to which this station is connected.
The present method of transmission to the medium by each station comprises the steps of: assigning each station a unique set of initial access numbers; assigning each station a set of current access numbers representing the station's set of initial access numbers and the number of frames received and transmitted by the station after the sync-signal has been received or transmitted; starting an access timer at each station upon detecting the absence of transmission on all channels connected to the station; stopping the count on the access timer at each station upon detecting the presence of transmission on a channel connected to the station; comparing the access timer count of each station with a value of TFR, representative of the station's set of current access numbers and the network time slot TS, a function of the network parameters; comparing the access timer count of each station with a value of TSS, representative of the stations' set of current access numbers, the number of stations on the network and the network time slot TS; opening an access window of predetermined duration when the access timer of a station reaches a value equal to the TFR; permitting transmission of a frame from a station to all output channels, to which the transmitting means of this station is connected when the access window of this station is open; retransmitting from each station input data received, after an idle period, from an input channel where the data has appeared first, to all other channels to which the transmitting means of this station is connected; transmitting the sync-signal from a station to all channels to which the transmitting means of this station is connected, starting when the access timer of this station reaches the value of TSS.